天鹅会面 [BFS+SPFA]

Problem

两头白天鹅生活在一个部分湖面结了冰的湖泊中，湖面的形状为一个长方形，并且被分割成R行C列的小方格，某些方格中结了冰，这样的方格称之为冰格，其余的方格称之为水格。

冬天过去了，湖面上的冰渐渐开始溶解了，每一天与水相邻的冰格就将消融而转化为水格。所谓两个方格相邻是指它们在水平或垂直方向有公共边，两个呈对角的方格是不相邻的。

白天鹅只能在水中沿水平或垂直方向游动，写一个程序判断多少天后两只白天鹅才能够相会。

输入

输入文件第一行包含两个用空格隔开的整数R 和C，其中1≤R,C≤1500，接下来的R行每行包含C个字符，描述湖面的初始状态，‘·’表示水格，‘X’表示冰格，‘L’表示一只白天鹅。

输出

输出文件仅一行包含一个整数表示两只白天鹅等到相邻那一天所需的天数。

样例

_SWAN.IN_

8 17

…XXXXXX..XX.XXX

….XXXXXXXXX.XXX

…XXXXXXXXXXXX..

..XXXXX.LXXXXXX..

.XXXXXX..XXXXXX..

XXXXXXX…XXXX…

..XXXXX…XXX….

….XXXXX.XXXL…

_SWAN.OUT_

Solution

这道题一个很简单的想法就是，先用BFS求出每个点消融的时间。对于本来就是水域的点，消融时间为0。注意到天鹅只能按照横轴或者纵轴移动，并且瞬间移动无限远，因此只要判定两只天鹅的最短时间即可。考虑SPFA的模型，我们只需将松弛距离的操作改为松弛时间的操作即可，在融冰的时间与当前最短时间中取max即可。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#define MAXN 1500 + 5
using namespace std;
int R, C;
char Map[MAXN][MAXN];
int melt[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dis[MAXN][MAXN];
struct node
{
	int x, y;
	node(int x = 0, int y = 0)
	{
		this->x = x;
		this->y = y;
	}
};
queue <node> Q1;
queue <node> Q2;
node loc[3];
int tot = 0;
char getch()
{
	char t;
	for (t = getchar();t != '.' && t != 'X' && t != 'L'; t = getchar());
	return t;
}
inline void BFS()
{
	memset(vis, 0, sizeof vis); 
	while (Q1.size())
	{
		int x = Q1.front().x, y = Q1.front().y;
		if (x > 1 && !vis[x - 1][y] && melt[x][y] + 1 < melt[x - 1][y])
		{
			melt[x - 1][y] = melt[x][y] + 1;
			vis[x - 1][y] = true;
			Q1.push(node(x - 1, y));
		}
		if (x < R && !vis[x + 1][y] && melt[x][y] + 1 < melt[x + 1][y])
		{
			melt[x + 1][y] = melt[x][y] + 1;
			vis[x + 1][y] = true;
			Q1.push(node(x + 1, y));
		}
		if (y > 1 && !vis[x][y - 1] && melt[x][y] + 1 < melt[x][y - 1])
		{
			melt[x][y - 1] = melt[x][y] + 1;
			vis[x][y - 1] = true;
			Q1.push(node(x, y - 1));
		}
		if (y < C && !vis[x][y + 1] && melt[x][y] + 1 < melt[x][y + 1])
		{
			melt[x][y + 1] = melt[x][y] + 1;
			vis[x][y + 1] = true;
			Q1.push(node(x, y + 1));
		}
		Q1.pop(); 
	}
}
inline SPFA(int x, int y)
{
	memset(vis, 0, sizeof vis);
	dis[x][y] = 0;
	Q2.push(node(x, y));
	vis[x][y] = true;
	while (Q2.size())
	{
		int a = Q2.front().x, b = Q2.front().y;
		Q2.pop();
		vis[a][b] = false;
		if (a > 1 && dis[a][b] < dis[a - 1][b] && dis[a - 1][b] != melt[a - 1][b])
		{
			dis[a - 1][b] = max(dis[a][b], melt[a - 1][b]);
			if (!vis[a - 1][b])
				Q2.push(node(a - 1, b)), vis[a - 1][b] = true;
		}
		if (a < R && dis[a][b] < dis[a + 1][b] && dis[a + 1][b] != melt[a + 1][b])
		{
			dis[a + 1][b] = max(dis[a][b], melt[a + 1][b]);
			if (!vis[a + 1][b])
				Q2.push(node(a + 1, b)), vis[a + 1][b] = true;
		}
		if (b > 1 && dis[a][b] < dis[a][b - 1] && dis[a][b - 1] != melt[a][b - 1])
		{
			dis[a][b - 1] = max(dis[a][b], melt[a][b - 1]);
			if (!vis[a][b - 1])
				Q2.push(node(a, b - 1)), vis[a][b - 1] = true;
		}
		if (b < C && dis[a][b] < dis[a][b + 1] && dis[a][b + 1] != melt[a][b + 1])
		{
			dis[a][b + 1] = max(dis[a][b], melt[a][b + 1]);
			if (!vis[a][b + 1])
				Q2.push(node(a, b + 1)), vis[a][b + 1] = true;
		}
	}
}
int main(int argc, char **Argv)
{
	freopen("swan.in", "r", stdin);
	freopen("swan.out", "w", stdout);
	cin >> R >> C;
	memset(dis, 0x3F, sizeof dis);
	memset(melt, 0x3F, sizeof melt);
	for (int i = 1; i <= R; ++i)
	{
		for (int j = 1; j <= C; ++j)
		{
			char p = getch();
			if (p == '.')
			{
				Q1.push(node(i, j));
				vis[i][j] = true;
				melt[i][j] = 0;
			}
			if (p == 'L')
			{
				vis[i][j] = true;
				melt[i][j] = 0;
				loc[++tot].x = i;
				loc[tot].y = j;
				Q1.push(node(i, j));
			}
		}
	}
	BFS();
	SPFA(loc[1].x, loc[1].y);
	cout << dis[loc[2].x][loc[2].y] << endl;
	return 0;
}